import javax.swing.tree.TreeNode;
import java.util.LinkedList;
import java.util.Queue;

class Node{
    public char val;
    public Node left;
    public Node right;
    public Node(char val) {
        this.val = val;

    }

}

public class TreeNode0823 {
    public Node createTree(){
        Node A = new Node('A');
        Node B = new Node('B');
        Node C = new Node('C');
        Node D = new Node('D');
        Node E = new Node('E');
        Node F = new Node('F');
        Node G = new Node('G');
        Node H = new Node('H');
        A.left = B;
        A.right = C;
        B.left = D;
        B.right = E;
        C.left = F;
        C.right = G;
        E.right = H;
        return A;
    }
    void preOrderTraversal(Node root){
        if (root == null){
            return;
        }
        System.out.print(root.val + " ");
        preOrderTraversal(root.left);
        preOrderTraversal(root.right);

    }
    void inOrderTraversal(Node root){
        if (root == null){
            return;
        }
        inOrderTraversal(root.left);
        System.out.print(root.val + " ");

        inOrderTraversal(root.right);

    }
    void postOrderTraversal(Node root){
        if (root == null){
            return;
        }
        postOrderTraversal(root.left);
        postOrderTraversal(root.right);
        System.out.print(root.val + " ");
    }
    int size(Node root){
        if (root == null){
            return 0;
        }
        return size(root.left) + size(root.right) + 1;
    }

    /*int count = 0;
    int size(Node root){

        if (root == null){
            return 0;
        }
        count++;
        size(root.right);
        size(root.left);
        return count;
    }*/
    int getSize2(Node root){
        if (root == null){
            return 0;
        }
        if (root.right == null && root.right == null){
            return 1;
        }
        return getSize2(root.left) + getSize2(root.right);

    }
    int getKLevelSize(Node root,int k){
        if (root == null || k <= 0){
            return 0;
        }
        if (k == 1){
            return 1;
        }
        return getKLevelSize(root.left, k-1) + getKLevelSize(root.right,k-1);



    }
    int getHeight(Node root){
        if (root == null){
            return 0;
        }
        int left = getHeight(root.left);
        int right = getHeight(root.right);
        return left > right ? left  + 1 : right + 1;
    }
     Node find(Node root, char val){
         if (root == null){
             return null;
         }
         if (root.val == val){
             return root;
         }
         return null;
    }
    /*boolean isCompleteTree(Node root){
        if (root == null){
            return  true;
        }
        Queue<Node> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()){
            Node cur = queue.poll();
            if (cur != null){
                queue.offer(root.right);
                queue.offer(root.left);
            }else {
                break;
            }

        }
        while (!queue.isEmpty()){
            Node top = queue.peek();
            if (top != null){
                return false;
            }else {
                queue.poll();
            }

        }
        return true;


    }*/
    boolean isCompleteTree(Node root){
        if (root == null){
            return true;
        }
        Queue<Node> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()){
            Node cur  = queue.poll();
            if (cur != null){
                queue.offer(root.left);
                queue.offer(root.right);
            }else {
                break;
            }
        }
        while (!queue.isEmpty()){
            Node top = queue.peek();
            if (top != null){
                return false;
            }else {
                queue.poll();
            }

        }
        return true;
    }





}
